//如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：
//
//
// n >= 3
// 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
//
//
// 给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
//
// （回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8]
//是 [3, 4, 5, 6, 7, 8] 的一个子序列）
//
//
//
//
//
//
// 示例 1：
//
//
//输入: arr = [1,2,3,4,5,6,7,8]
//输出: 5
//解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
//
//
// 示例 2：
//
//
//输入: arr = [1,3,7,11,12,14,18]
//输出: 3
//解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。
//
//
//
//
// 提示：
//
//
// 3 <= arr.length <= 1000
// 1 <= arr[i] < arr[i + 1] <= 10^9
//
//
// Related Topics 数组 哈希表 动态规划 👍 369 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function lenLongestFibSubseq(arr: number[]): number {
    /*
    ? 定义 f[i][j] 为使用 arr[i] 为斐波那契数列的最后一位，使用 arr[j] 为倒数第二位（即 arr[i] 的前一位）时的最长数列长度。
    ? f[i][j] = max(3, f[j][t] + 1)  t为arr[i] - arr[j]值的坐标
     */
    let n = arr.length, ans = 0
    //? hash表记录每个值的索引
    const map: Map<number, number> = new Map<number, number>()
    for (let i = 0; i < n; i++) map.set(arr[i], i)
    let f: number[][] = new Array<Array<number>>(n)
    for (let i = 0; i < n; i++) {
        f[i] = new Array<number>(n).fill(0)
        //? 假设当前最大长度为 ans，只有当 j+2>ans，我们才有必要往下搜索，j+2 的含义为以 arr[j] 为斐波那契数列倒数第二个数时的理论最大长度。
        for (let j = i - 1; j >= 0 && j + 2 >= ans; j--) {
            const t = arr[i] - arr[j]
            if (!map.has(t)) continue
            const idx = map.get(t)
            //? 不满足单调递增 这也是为什么j从大到小遍历
            if (idx >= j) break
            f[i][j] = Math.max(3, f[j][idx] + 1)
            ans = Math.max(ans, f[i][j])
        }
    }
    return ans
};

//leetcode submit region end(Prohibit modification and deletion)
